// https://leetcode.cn/problems/minimum-absolute-difference-in-bst/

package binarytree

func getMinimumDifference(root *TreeNode) int {
	// 思路：中序遍历二叉搜索树，得到一个有序数组
	// 然后遍历这个数组，计算相邻元素的差值，找到最小的差值
	var prev *TreeNode
	minDiff := int(^uint(0) >> 1) // 初始化为最大整数

	var inorder func(node *TreeNode)
	inorder = func(node *TreeNode) {
		if node == nil {
			return
		}
		// 先处理左子节点，如果是nil，此处其实啥也没干
		inorder(node.Left)
		// 处理当前节点
		// 如果 prev 不是 nil，说明之前已经按顺序访问过几个节点了，prev指向的是上一个节点
		// 计算当前节点和上一个节点的差值
		// 如果 prev 是 nil，说明这是第一个节点，不能计算差值
		if prev != nil {
			diff := node.Val - prev.Val
			if diff < minDiff {
				minDiff = diff
			}
		}
		// 更新 prev 为当前节点
		// 这样在下次访问时，prev 就是当前节点了
		// 这一步是关键，prev 需要在访问当前节点后更新
		// 这样才能保证在下次访问时，prev 是当前节点的前一个节点
		// 也就是中序遍历的顺序是 左 -> 当前 -> 右
		prev = node
		// 最后处理右子节点
		// 右子节点的处理同样是递归调用 inorder 函数
		// 这样就能保证所有节点都被访问到
		// 处理完左子节点后，处理当前节点，再处理右子节点
		// 这样就能保证中序遍历的顺序
		// 也就是左子树 -> 当前节点 -> 右子树
		inorder(node.Right)
	}

	inorder(root)
	return minDiff
}

// 这个函数的时间复杂度是 O(n)，其中 n 是树中的节点数，因为每个节点都被访问一次。
// 空间复杂度是 O(h)，其中 h 是树的高度，递归调用栈的空间复杂度。
// 由于二叉搜索树的性质，中序遍历得到的节点值是有序的，因此相邻节点的差值就是最小的绝对差值。
// 这种方法的优点是简单且高效，适用于二叉搜索树。
// 如果树是平衡的，空间复杂度可以认为是 O(log n)，但在最坏情况下（例如链表形状的树），空间复杂度为 O(n)。
